package com.zlk.algorithm.huawei.leetcode.unionAndFind;

import org.junit.Test;

import java.util.HashMap;
import java.util.Stack;

/**
 * @program: algorithm
 * @ClassName Code60_NumberOfIslands
 * @description:https://leetcode.cn/problems/number-of-islands/
 * @author: slfang
 * @create: 2025-01-21 09:30
 * @Version 1.0
 **/
public class Code60_NumberOfIslands {

    @Test
    public void test(){
        char[][] grid = new char[][]
                {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}}
                ;
        System.out.println(numIslands(grid));
    }

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        UnionAndFind unionAndFind = new UnionAndFind(grid);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j]=='1'){
                    //上
                    if(i-1>=0&&grid[i-1][j]=='1'){
                        String curIndex = unionAndFind.getIndex(i,j);
                        String upIndex = unionAndFind.getIndex(i-1,j);
                        unionAndFind.union(curIndex,upIndex);
                    }
                    //左
                    if(j-1>=0&&grid[i][j-1]=='1'){
                        String curIndex = unionAndFind.getIndex(i,j);
                        String leIndex = unionAndFind.getIndex(i,j-1);
                        unionAndFind.union(curIndex,leIndex);
                    }
                }
            }
        }
        return unionAndFind.sets;
    }

    class UnionAndFind{
        public HashMap<String,String> father;
        public HashMap<String,Integer> size;
        public int sets;

        public String getIndex(int i,int j){
            return "i:"+i+"j:"+j;
        }

        public UnionAndFind(char[][] grid){
            father = new HashMap<>();
            size = new HashMap<>();
            int n = grid.length;
            int m = grid[0].length;
            sets = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if(grid[i][j]=='1'){
                        String key = getIndex(i,j);
                        father.put(key,key);
                        size.put(key,1);
                        sets++;
                    }
                }
            }
        }

        public boolean isConnect(String a,String b){
            return findFather(a).equals(findFather(b));
        }

        public String findFather(String cur) {
            Stack<String> stack = new Stack<>();
            while (cur!=father.get(cur)){
                stack.push(cur);
                cur = father.get(cur);
            }
            while (!stack.isEmpty()){
                father.put(stack.pop(),cur);
            }
            return cur;
        }

        public void union(String a,String b){
            String fatherA = findFather(a);
            String fatherB = findFather(b);
            if(!isConnect(fatherA,fatherB)){
                Integer sizeA = size.get(fatherA);
                Integer sizeB = size.get(fatherB);
                if(sizeA>=sizeB){
                    father.put(fatherB,fatherA);
                    size.put(fatherA,sizeA+sizeB);
                }else{
                    father.put(fatherA,fatherB);
                    size.put(fatherB,sizeA+sizeB);
                }
                sets--;
            }
        }

    }


}
